class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        /* 暴力超时了，真尴尬
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] > prices[i]) {
                    ans = Math.max(ans, prices[j] - prices[i]);
                }
            }
        }
        */
        int[] maxAfterI = new int[prices.length];
        maxAfterI[prices.length - 1] = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            maxAfterI[i] = Math.max(prices[i+1], maxAfterI[i+1]);
        }
        for (int i = 0; i < prices.length - 1; i++) {
            ans = Math.max(ans, maxAfterI[i] - prices[i]);
        }
        return ans;
    }
}
